← All Articles

[SW Expert Academy] 1812. 수정이의 타일 자르기

Posted on

문제 :

인테리어에 관심이 많은 수정이는 벽에 타일을 붙이려고 한다.

수정이는 변의 크기가 2의 지수 승(2^k)인 정사각형 N개가 필요하다.

수정이는 동네 가게에서 타일을 구입하려고 하는데,

수정이가 간 가게에서는 변의 크기가 M인 정사각형 타일 밖에 팔지 않아서

어쩔 수 없이 직접 잘라서 원하는 크기의 타일로 만들고자 한다.

타일을 자르는 방향은 반드시 타일의 변과 수직-수평으로 잘라야 한다.

이 때, 수정이는 최소 몇 개의 타일을 사야 원하는 크기의 타일들을 만들어 낼 수 있을까?


입력 :

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M(1 ≤ N ≤ 500, 1 ≤ M ≤ 2^31 – 1) 이 공백 하나로 구분되어 주어진다.

두 번째 줄에는 N개의 음이 아닌 정수 S1, S2, … , SN (1 ≤ 2^Si ≤ M) 이 공백 하나로 구분되어 주어진다.


출력 :

각 테스트 케이스마다 ‘#t’(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고

한 칸을 띄운 후 타일 가게에서 최소 몇 개의 타일을 사야 하는지 출력한다.



풀이 :

굉장히 흥미로우면서도 계속되는 에러 케이스들 때문에 상당히 곤혹스러웠던 문제였다.

우선 가장 중요한 key point들을 짚어보았다.

  1. 기준 정사각형 타일을 잘라서 원하는 타일을 만들었을 때 자투리로 남은 나머지 타일 부분들을 저장해두고 다른 타일을 자투리 타일로 만들 수 있는지 확인하는 형태로 로직을 진행해야 한다. 아래 그림과 같이 초록색 타일을 만들려고 할 경우에는 (가로, 세로)형태가 (width, height - k), (width - k, k) 길이를 가지는 두 개의 사각형 타일 자투리가 발생한다. 원하는 타일을 만들 때마다 발생하는 자투리 타일 가로, 세로 길이들을 저장해두는 벡터를 만들고 이 벡터들을 훑으면서 타일을 만들 수 있는지 확인을 거친 후 자투리 타일로 원하는 타일을 만들 수 없을 때, 새로운 타일을 추가적으로 사용해야 한다.

image

  1. 원하는 사각형 타일들은 정렬 후 큰 사각형 타일부터 만들어야 한다. 작은 타일부터 만들 경우 쓸 수 없는 자투리 타일들의 낭비가 늘어나기 때문이다.

본 문제에서 개인적으로 가장 힘든 부분은 자투리 타일들을 차례로 탐색하면서 원하는 타일을 만들 수 있는지 확인하는 과정이었다. 처음에는 시간복잡도를 줄이기 위해 자투리 타일 중에서 min(가로 길이, 세로 길이) 값이 가장 큰 자투리 타일부터 확인하도록 큐를 만들어 코드를 진행했다. 그런데 가로 세로를 구분하지 않고 큐에 집어넣다보니 많은 에러 케이스들이 발견되었다. 그리고 벡터에 차례로 자투리 타일들을 집어넣어 사용한 타일들을 표시해주는 방식으로 구현하더라도 큐를 사용한 방식과 시간복잡도가 크게 차이가 나지 않았다.



코드 :

코드 보기/접기 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<utility>
#include<queue>
 
#define pii pair<int, int>
 
using namespace std;
typedef struct RecNode {
    int width, height;
    bool used;
};
int n, stdsize;
 
int testCase() {
    vector<RecNode> remains;
    vector<int> squarevec;
    int input, tilecnt = 1, t;
    cin >> n >> stdsize;
 
    for (int i = 0; i < n; i++) {
        cin >> input;
        squarevec.push_back(pow(2, input));
    }
    sort(squarevec.begin(), squarevec.end(), greater<int>());
 
    remains.push_back(RecNode{stdsize, stdsize, false});
    for (int k = 0; k < n; k++) {
        int cyclesize = remains.size(), curlength = squarevec[k];
        for (t = 0; t < cyclesize; t++) {
            if (remains[t].used) continue;
            int width = remains[t].width, height = remains[t].height;
            if (width >= curlength && height >= curlength) {
                remains[t].used = true;
                remains.push_back(RecNode{width, height - curlength, false});
                remains.push_back(RecNode{width - curlength, curlength, false});
                break;
            }
        }
        if (t >= cyclesize) {
            tilecnt++;
            remains.push_back(RecNode{stdsize, stdsize - curlength, false});
            remains.push_back(RecNode{stdsize - curlength, curlength, false});
        }
    }
    return tilecnt;
}
 
int main() {
    int tc;
    cin >> tc;
    for (int k = 1; k <= tc; k++)
        cout << '#' << k << ' ' << testCase() << '\n';
    return 0;
}


AlgorithmalgorithmSW ExpertC++